#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>

template<typename dataType>
struct letterMove
{
    short dir;
    dataType letterFirst;
    dataType letterSecond;
    letterMove(short newDir, dataType newLetFirst, dataType newLetSecond)
    {
        dir = newDir;
        letterFirst = newLetFirst;
        letterSecond = newLetSecond;
    }
};

template<typename Iterator>
int easyDistance(Iterator firstBegin, Iterator firstEnd, Iterator secondBegin, Iterator secondEnd,
                 std::ostream &fout = std::cout)
{
    std::vector<size_t> upLine(firstEnd - firstBegin);
    std::vector<size_t> downLine(firstEnd - firstBegin);//Эти два массива не нужны, но тестировать с ними удобней
    std::vector< std::vector< letterMove<Iterator> > > upWay(firstEnd - firstBegin);
    std::vector< std::vector< letterMove<Iterator> > > downWay(firstEnd - firstBegin);

    if (*secondBegin == *firstBegin)
    {
        upLine[0] = 0;
    }
    else
    {
        upLine[0] = 1;
        upWay[0].push_back(letterMove<Iterator>(0, firstBegin, secondBegin));
    }

    for (size_t j = 1; j < upLine.size(); ++j)
    {
        upLine[j] = upLine[j - 1] + 1;
        upWay[j].push_back(letterMove<Iterator>(1, (firstBegin + j), secondBegin));
    }

    for (size_t i = 1; i < secondEnd - secondBegin; ++i)
    {
        for (size_t j = 0; j < upLine.size(); ++j)
            std::cout << " " << upLine[j];

        downLine[0] = upLine[0] + 1;
        downWay[0] = upWay[0];
        downWay[0].push_back(letterMove<Iterator>(2, firstBegin, (secondBegin + i)));

        for (size_t j = 1; j < downLine.size(); ++j)
        {
            if (upLine[j - 1] <= std::min(upLine[j], downLine[j - 1]))
            {
                if (*(secondBegin + i) == *(firstBegin + j))
                {
                    downLine[j] = upLine[j - 1];
                    downWay[j] = upWay[j - 1];

                }
                else
                {
                    downLine[j] = upLine[j - 1] + 1;
                    downWay[j] = upWay[j - 1];
                    downWay[j].push_back(letterMove<Iterator>(0, (firstBegin + j), (secondBegin + i)));
                }
            }
            else
            {
                if (upLine[j] < downLine[j - 1])
                {
                    downLine[j] = upLine[j] + 1;
                    downWay[j] = upWay[j];
                    downWay[j].push_back(letterMove<Iterator>(2, (firstBegin + j), (secondBegin + i)));
                }
                else
                {
                    downLine[j] = downLine[j - 1] + 1;
                    downWay[j] = downWay[j - 1];
                    downWay[j].push_back(letterMove<Iterator>(1, (firstBegin + j), (secondBegin + i)));
                }
            }
        }

        std::swap(upLine, downLine);
        std::swap(upWay, downWay);
        std::cout << "\n";
    }

    for (size_t j = 0; j < upLine.size(); ++j)
        std::cout << " " << upLine[j];
    std::cout << "\n";

    size_t fin = upLine.size() - 1;
    for (size_t i = 0; i < upWay[fin].size(); ++i)
    {
        if (upWay[fin][i].dir == 0)
            fout << *(upWay[fin][i].letterFirst) << " -> " << *(upWay[fin][i].letterSecond) << "\n";
        else if (upWay[fin][i].dir == 1)
            fout << *(upWay[fin][i].letterFirst) << " -> NULL\n";
        else
            fout << "NULL -> " << *(upWay[fin][i].letterSecond) << "\n";
    }

    return upLine[fin];
}

template<typename Iterator>
int hirshbergDistance(Iterator firstBegin, Iterator firstEnd, Iterator secondBegin, Iterator secondEnd,
                 std::ostream &fout = std::cout)
{
    if (firstEnd == firstBegin + 1)
        return 1;//secondEnd - secondBegin;
    return hirshbergDistance(firstBegin, firstBegin + (firstEnd - firstBegin)/2, secondBegin, secondEnd, fout) +
           hirshbergDistance(firstBegin + (firstEnd - firstBegin)/2, firstEnd, secondBegin, secondEnd, fout);
}

int main()
{
    std::string firstText;
    std::string secondText;

    std::cin >> firstText >> secondText;
    std::cout << easyDistance(firstText.begin(), firstText.end(), secondText.begin(), secondText.end()) << "\n";

    return 0;
}
